#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    bool validateBookSequences(vector<int>& putIn, vector<int>& takeOut)
    {
        std::stack<int> st;

        int n = putIn.size();
        int inIndex = 0, outIndex = 0;

        while (inIndex < n && outIndex < n)
        {
            if (!st.empty() && st.top() == takeOut[outIndex])
            {
                st.pop();
                ++outIndex;
            }
            else
            {
                st.push(putIn[inIndex]);
                ++inIndex;
            }
        }

        while (outIndex < n && !st.empty() && st.top() == takeOut[outIndex])
        {
            st.pop();
            ++outIndex;
        }

        return st.empty();
    }
};